package training;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
 * @Author liangzai
 * @Description:
 */
public class J25_5_11_training {
    static Scanner cin=new Scanner(System.in);
    //    static FastReader cin=new FastReader();
    static int N=100010,n;
    static List<Integer>[] tree=new List[N];
    static int[] arr=new int[N],val=new int[N];
    static int getN(int n)
    {
        int res=1,cnt=0;
        for(int i=2;i*i<=n;i++)
        {
            cnt=0;
            while (n%i==0)
            {
                n/=i;
                cnt++;
            }
            if((cnt&1)==1) res*=i;
        }
        if(n>1) res*=n;
        return res;
    }
    public static void main(String[] args) {
        Arrays.setAll(tree,i->new ArrayList<>());
        n=cin.nextInt();
        for(int i=1;i<=n;i++)
        {
            arr[i]=cin.nextInt();
            val[i]=getN(arr[i]);
        }
        for(int i=1;i<=n-1;i++)
        {
            int a=cin.nextInt();
            int b=cin.nextInt();
            tree[a].add(b);
            tree[b].add(a);
        }
        Queue<int[]> q=new ArrayDeque<>();
        q.add(new int[]{1,0});
        Map<Integer,Integer> map=new HashMap<>();
        int ans=0;
        while (!q.isEmpty())
        {
            int[] temp=q.poll();
            int node=temp[0],fa=temp[1];
            if(tree[node]!=null&&tree[node].size()>=2)
            {
                for(int i:tree[node])
                {
                    if(i!=fa)
                        map.put(val[i],map.getOrDefault(val[i],0)+1);
                }
            }
            for(int i:tree[node])
            {
                if(i!=fa)
                    q.add(new int[]{i,node});
            }
            for(Map.Entry<Integer,Integer> entry:map.entrySet())
                ans+=entry.getValue()-1;
            map.clear();
        }

        System.out.println(ans);

    }
}
